#ifndef _Tree_H_
#define _Tree_H_

/******************************************************************************

Description:
  Tree class. Intended for using in fp-trees.
Author: Tayfun Sen
Website: http://blog.tayfunsen.com
 
 *****************************************************************************/

// Standard libraries.
#include <iostream>
#include <ext/hash_map>
// Boost libraries for serializing.
#include <boost/tokenizer.hpp>
#include <boost/archive/tmpdir.hpp>
#include <boost/archive/text_oarchive.hpp>
#include <boost/archive/binary_oarchive.hpp>
#include <boost/serialization/export.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <boost/serialization/base_object.hpp>
#include <boost/serialization/utility.hpp>
#include <boost/serialization/hash_map.hpp>
#include <boost/serialization/map.hpp>
#include <boost/serialization/string.hpp>
#include <boost/mpi.hpp>
// Custom libraries.
#include "shared.hpp"
#include "HeaderInfo.hpp"
#include "Node.hpp"


using namespace std;
using namespace __gnu_cxx;

class Tree {
    public:
        // Root will not hold any value.
        Tree() : root(new Node("root", -1)) {}
        
        // We need a copy constructor for Tree. Since it is used when passed by
        // value, returned by value etc. This one uses the copy assignment 
        // operator for constructing. See copy-assignment op.
        Tree(const Tree & t) : root(new Node("root", -1)) {
            *this = t; }

        // Copy assignment operator.
        const Tree & operator= (const Tree & rhs);

        ~Tree() {
            makeEmpty(); }

        void makeEmpty() {
            makeEmpty(root);
            // Also remove the header information in hash table and vector.
            headerVector.clear();
            headerTable.clear();
            itemCounts.clear();
        }

        int insert(vector<string> *, int count = 1);

        Node * getRoot() const {
            return root; }

        void insertSubTree(Node *, Node *);

        // Used when reducing trees. They are merged using this method.
        void merge(Tree &);

        void print();

        hash_map<string, HeaderInfo *> & getHeaderTable() {
           return headerTable; } 

        vector<HeaderInfo *> & getHeaderVector() {
            return headerVector; }

        void setItemCounts(hash_map<string, int> & itemCountsArg) {
            // Copy the hash map to the tree.
            itemCounts = itemCountsArg;
        }

        int getItemCount(string item) {
            return itemCounts[item]; }

        hash_map<string, int> * getItemCountsP() {
            return &itemCounts; }

        hash_map<string, int> & getItemCountsR() {
            return itemCounts; }

        void skipHeaderInfo(string item) {
            headerTable[item]->skip = true;
        }

        // For debugging.
        void printHeaderTable();
        void printHeaderVector();

    private:
        friend class boost::serialization::access;
        template<class Archive>
            void serialize(Archive & ar, const unsigned int version) {
                ar & root;
                // The below NEED TO BE serialized since both header data
                // are reconstructed while merging and item counts are
                // added after merging BUT the whole constructed tree is
                // sent to other nodes in the end. Thus everything needs
                // to be serialized.
                ar & headerTable;
                ar & headerVector;
                ar & itemCounts;
            }
        //*****************************************
        //************ data ***********************
        //*****************************************
        // Pointer to the root node.
        Node * root;
        // Header table is a part of the tree so that the tree can manipulate 
        // it as items are inserted. It is a hash map so that one can easily 
        // obtain and manipulate the needed header info. Note that header info
        // are also stored in header vector where we don't need to have hash 
        // access but would rather have ordered access.
        hash_map<string, HeaderInfo *> headerTable;
        // Header Vector has essentially the same thing as above header hash
        // table. It exists to simplify partitioning item sets and also for
        // enabling top-down mining of items. There is not too much cost
        // associated with this because it takes up small space: 
        // (pointer size) * (number of items above threshold) 
        // ie. Both header vector and hash points to the same HeaderInfo.
        vector<HeaderInfo *> headerVector;
        // It's wise to put item counts inside a tree because it will be used 
        // in the second phase when projecting trees. It is cumbersome to put
        // item counts inside header info and manage them there. Therefore,
        // we copy it from reduced counts.
        hash_map<string, int> itemCounts;

        //*****************************************
        //************ methods ********************
        //*****************************************
        // The argument is a reference to a pointer
        // for a good reason. Think about it!
        int makeEmpty(Node * & t);
        void insertHeaderInfo(Node * node);
        // Duplicate creates a new tree which is the same as the one given as
        // its parameter and returns the root node. The children are also 
        // inserted to the header table. So it does pretty much the housekeeping
        // as well.
        Node * duplicate(const Node *);
        void printRec(Node *);
};

#endif
